public class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    //当前搜索树的根节点
    public TreeNode root = null;
    //查找结点
    public TreeNode search(int val){
        TreeNode cur = root;
        while(cur != null){
            if(cur.val > val){
                cur = cur.left;
            }else if(cur.val < val){
                cur = cur.right;
            }else {
                return cur;
            }
        }
        return null;
    }
    //插入结点
    public void insert(int val){
        if(root == null){
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        TreeNode p = null;
        while(root != null) {
            p = cur;
            if (cur.val > val) {
                cur = cur.left;
            } else if (cur.val < val) {
                cur = cur.right;
            } else {
                return;
            }
        }
        if(p.val > val){
            p.left = new TreeNode(val);
        }else if(p.val < val){
            p.right = new TreeNode(val);
        }
    }
    //删除结点(难点)
    public void remove(int val){
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null){
            if(cur.val > val){
                cur = cur.left;
            }else if(cur.val < val){
                cur = cur.right;
            }else {
                removeNode(cur,parent);
                return;
            }
            parent = cur;
        }
        return;
    }
    //删除结点(难点)
    public void removeNode(TreeNode cur,TreeNode parent){
        if(cur.left == null){
            if(cur == root){
                root = root.right;
            }else if(cur == parent.left){
                parent.left = cur.right;
            }else if(cur == parent.right){
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            if(cur == root){
                root = root.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else if(cur == parent.right){
                parent.right = cur.left;
            }
        }
        TreeNode node = cur.right;
        TreeNode nodeParent = cur;
        while(node.left != null){
            nodeParent = node;
            node = node.left;
        }
        cur.val = node.val;
        if(node == nodeParent.left){
            nodeParent.left = node.right;
        }else if(node == nodeParent.right){
            nodeParent.right = node.right;
        }
    }
}











